/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName   : Leetcode448 
 * @author      : ganwei 
 * @date        : 2020年5月2日
 * @Description : Leetcode448 找到所有数组中消失的数字
 */
public class Leetcode0448 {
	/**
	 * -解题思路,采用hashmap，但该方法使用了O(N)的空间，不满足题目要求
	 */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
    	
    	
    	return null;
    }
    
	/**
	 * -解题思路,在原有数组上进行修改，标记思路为 将 nums[abs(nums[i])-1]*-1
	 */
    public static List<Integer> findDisappearedNumbers_1(int[] nums) {
    	for(int i=0; i < nums.length; i++){
    		if(nums[Math.abs(nums[i])-1] > 0){
    			nums[Math.abs(nums[i])-1] *= -1;
    		}
    	}
    	List<Integer> list = new LinkedList<Integer>();
    	for(int i=1; i <= nums.length; i++){
    		if(nums[i-1] > 0){
    			list.add(i);
    		}
    	}
    	
    	return list;
    }    
    
    
    public static void main(String args[]){
    	
    }
}
